//
// Description: 5983. 同时运行 N 台电脑的最长时间
// Created by Loading on 2022/1/16.
//

#include <bits/stdc++.h>

using namespace std;

/* 数学 */
long long maxRunTime(int n, vector<int> &batteries) {
    // 电池电量总和
    long long sum = accumulate(batteries.begin(), batteries.end(), 0ll);
    // 由大到小排序
    sort(batteries.begin(), batteries.end(), greater<>());
    for (auto &battery : batteries) {
        // 电量大于平均值，说明可以一直给一台电脑供电，可以直接移除
        if (battery >= sum / n) {
            sum -= battery;
            --n;
        } else {
            break;
        }
    }

    return sum / n;
}

/* 二分 */
long long maxRunTime_BS(int n, vector<int> &batteries) {
    // 检查当前时间是否满足要求
    auto check = [&](long long t) {
        long long sum = 0;
        for (auto &battery : batteries) {
            // 每个电池最多运行 t 时间
            sum += min(t, (long long) battery);
        }

        // 如果 n 个电脑同时运行 t 时间，总和小于等于 sum，则 t 满足要求
        return t * n <= sum;
    };

    long long l = 1, r = 1e14;
    while (l < r) {
        long long mid = (l + r + 1) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    return l;
}

int main() {
    int n = 2;
    vector<int> batteries = {1, 1, 1, 1};
    auto res = maxRunTime(n, batteries);
    cout << res << endl;
    res = maxRunTime_BS(n, batteries);
    cout << res << endl;

    return 0;
}
